﻿namespace Leetcode.N0079;
public class Solution
{
    public bool Exist(char[][] board, string word)
    {
        if (string.IsNullOrEmpty(word))
        {
            return false;
        }

        var visited = new bool[board.Length][];
        for (int row = 0; row < board.Length; row++)
        {
            visited[row] = new bool[board[0].Length];
        }

        for (int row = 0; row < board.Length; row++)
        {
            for (int col = 0; col < board[row].Length; col++)
            {
                if (board[row][col] != word[0])
                {
                    continue;
                }
                visited[row][col] = true;
                if (this.Find(board, row, col, word, 1, visited))
                {
                    return true;
                }
                visited[row][col] = false;
            }
        }
        return false;
    }

    private bool Find(char[][] board, int row, int col, string word, int nextWordIndex, bool[][] visited)
    {
        if (nextWordIndex >= word.Length)
        {
            return true;
        }
        var findChar = word[nextWordIndex];

        var next = new (int row, int col)[] { (row - 1, col), (row + 1, col), (row, col - 1), (row, col + 1) };
        nextWordIndex++;
        foreach (var n in next)
        {
            if (n.row < 0 || n.row >= board.Length || n.col < 0 || n.col >= board[0].Length)
            {
                continue;
            }
            if (findChar != board[n.row][n.col])
            {
                continue;
            }
            if (visited[n.row][n.col])
            {
                continue;
            }

            visited[n.row][n.col] = true;
            if (this.Find(board, n.row, n.col, word, nextWordIndex, visited))
            {
                return true;
            }
            visited[n.row][n.col] = false;
        }
        return false;
    }
}
